package sort;

/**
 * @author qiss
 * @create 2018-05-07 12:06
 **/
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {49,38,65,97,76,13,27,49};
        heapSort(array,false);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }

    /**
     * 堆排序算法
     * @param array
     * @param inverse true为倒排，false为正排
     */
    private static void heapSort(int[] array, boolean inverse) {
        //初始堆
        for (int i = (array.length-1) >> 2; i >= 0; i--) {
            if(inverse){
                heapAdjustS(array,i,array.length);
            }else{
                heapAdjustB(array,i,array.length);
            }
        }
        //初始化堆结束
        for (int i = array.length - 1; i >= 0 ; i--) {
            //交换堆顶元素array[0]和堆中最后一个元素
            int tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
            if(inverse){
                heapAdjustS(array,0,i);
            }else{
                heapAdjustB(array,0,i);
            }

        }
    }

    /**
     * 大顶堆
     * @param array 为待调整的堆数组
     * @param s 待调整的数组元素的位置
     * @param length 数组的长度
     */
    private static void heapAdjustB(int[] array, int s, int length) {
        int tmp = array[s];
        int child = s << 2 + 1;
        while(child < length){
            if(child + 1 < length && array[child] < array[child+1]){
                child++;
            }
            if(array[child] > array[s]){
                array[s] = array[child];
                s = child;
                array[child] = tmp;
                child = s >>2 +1;
                if(child >= length){
                    System.out.println("没有子孩子了，调整结束");
                }else{
                    System.out.println("继续与新的子孩子进行比较");
                }
            }else{
                System.out.println("子孩子均比其小，调整结束");
                break;
            }
        }
    }

    /**
     * 小顶堆
     * @param array
     * @param s
     * @param length
     */
    private static void heapAdjustS(int[] array, int s, int length) {
        int tmp = array[s];
        int child = s << 2 +1;
        while(child < length){
            if(child + 1 < length && array[child] > array[child+1]){
                child ++;
            }
            if (array[s] > array[child]) {
                array[s] = array[child];
                child = s >> 2 + 1;
                array[child] = array[s];
                if(child >= length){
                    System.out.println("没有子孩子了，调整结束");
                }else{
                    System.out.println("继续与新的子孩子进行比较");
                }
            }else{
                System.out.println("子孩子均比其大，调整结束");
            }
        }
    }
}
